package fun.coding.baozi.practice;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class RegularExpressionMatching {
    
    public static void returnAllUsingStack(String input) {
        if(input == null || input.isEmpty()){
            return;
        }
        
        Stack<Integer> positionToReVisit = new Stack<Integer>();
        positionToReVisit.push(-1);
        
        StringBuilder currentString = new StringBuilder();
        int currStartPosition = 0;
        
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '?') {
                positionToReVisit.push(i);
                currentString.append(0);
                break;
            }
            currentString.append(input.charAt(i));
            currStartPosition++;
        }
        
        if (currentString.length() == input.length()) {
            System.out.println(currentString);
            return;
        }
        
        while (!positionToReVisit.isEmpty()) {
            for (int i = currStartPosition + 1; i < input.length(); i++) {
                if (input.charAt(i)== '?') {
                    currentString.append('0');
                    positionToReVisit.push(i);
                } else {
                    currentString.append(input.charAt(i));
                }
            }
            
            if (currentString.length() == input.length()) {
            	System.out.println(currentString);
            }
            
            currStartPosition = positionToReVisit.pop();
            
            if (currStartPosition == -1) break;
            
            currentString = new StringBuilder(currentString.substring(0, currStartPosition));
            currentString.append('1');
        }         
        
        return;
    }

    
    public static void returnAll(String input) {
        if(input == null || input.isEmpty()) {
            return;
        }
        
        StringBuilder current_string = new StringBuilder();
        returnAllRecursion(input, 0, current_string);
    }

    public static void returnAllRecursion(String input, int current_location, StringBuilder current_string){
        if (input.length() == current_location) {
            System.out.println(current_string);
            return;
        }
        
        while (input.length() > current_location && input.charAt(current_location) != '?') {
            current_string.append(input.charAt(current_location));
            current_location++;
        }
        
        if (input.length() == current_location) {
            System.out.println(current_string);
            current_string.deleteCharAt(current_location - 1);
            return;
        }
        
        if (input.charAt(current_location) == '?') {
            current_string.append(0);
            returnAllRecursion(input, current_location + 1, current_string);
            current_string.deleteCharAt(current_string.length() - 1);
            current_string.append(1);
            returnAllRecursion(input, current_location + 1, current_string);
            current_string.deleteCharAt(current_string.length() - 1);
        }
    }
    
    public static void main(String[] args) {
       
        /*
        returnAll("0100");
        System.out.println("---------------");
        returnAll("01??");
        System.out.println("---------------");
        returnAll("???0");
        System.out.println("---------------");
        returnAll("????");
        */
        returnAllUsingStack("0100");
        System.out.println("---------------");
        returnAllUsingStack("01??");
        System.out.println("---------------");
        returnAllUsingStack("???0");
        System.out.println("---------------");
        returnAllUsingStack("????");
        // matchingQuestionMark("????");
    }
    
    // Print out all the possible matchings
    /*
        input: 100100?00?
        output: {1001000000,1001000001,1001001000,1001001001}
    */
    public static void matchingQuestionMark(String s) {
        if (s == null || s.isEmpty()) return;
        
        List<Integer> questionMarkIndex = new ArrayList<Integer>();
        int totalQuestionMarkCount = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '?') {
                totalQuestionMarkCount++;
                questionMarkIndex.add(i);
            }
        }
        
        if (totalQuestionMarkCount == 0) return;
        
        for (int i = 0; i < (1 << totalQuestionMarkCount); i++) {
            StringBuilder sb = new StringBuilder(s);
            int j = 0;
            int temp = i;
            while (j < totalQuestionMarkCount) {
                int index = questionMarkIndex.get(j);
                if ((temp & 1) == 0) {
                    sb.replace(index, index + 1, "0");
                } else {
                    sb.replace(index, index + 1, "1");
                }
                j++;
                temp = temp >> 1;    
                
            }
            System.out.println(sb.toString());
        }
    }

}
